package com.captain.lc.动态规划;

/**
 * Des:
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * @author XL
 * @Date 2021/10/25 14:54
 */
public class LongestPalindrome05 {

    public String longestPalindrome(String s) {
        //解题思路,纵向遍历,确保dp[i +1][j -1]是没有问题的
        if (s == null || s.length() <= 1) return s;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int longest = 0;
        String res = null;
        //按照列来遍历
        for (int j = 0; j < len; j++) {
            // i -- j的范围内
            //第一次就是 第一列第一行
            for (int i = 0; i <= j; i++) {
                if (s.charAt(j) == s.charAt(i)) {
                    //例如 a a , 肯定是
                    if (j - i < 3) {
                        dp[i][j] = true;
                        int tp = j+1 - i;
                        if (tp > longest) {
                            String s1 = s.substring(i, j + 1);
                            res = s1;
                            longest = tp;
                        }
                    } else {
                        //往里缩进 i + 1 ,j -1
                        //往前一列, 往下一列
                        dp[i][j] = dp[i + 1][j - 1];
                        if (dp[i][j]) {
                            int tp = j+1 - i;
                            if (tp > longest) {
                                String s1 = s.substring(i, j + 1);
                                res = s1;
                                longest = tp;
                            }
                        }
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new LongestPalindrome05().longestPalindrome("ccc"));

    }
}
